#include "DoubleLinkList.h"
#include <stdio.h>
#include <stdlib.h>

//创建节点的接口
DLNode * CreateNode(ElementType element)
{
    DLNode *newNode = (DLNode*)malloc(sizeof(DLNode));
    if(newNode == NULL)
    {
        printf("create Node malloc error!\n");
        return NULL;
    }
    newNode->data = element;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}


void InitDLlist(DLlist *list)
{
    //void*传空指针
    list->head = list->tail = CreateNode(NULL);
    list->len = 0;
}

void InsertDLlistTail(DLlist *list, ElementType element)
{
    DLNode *newNode = CreateNode(element);
    //判断是否创建时就出错
    if(newNode == NULL)
    {
        return;
    }
    list->tail->next = newNode;
    newNode->prev = list->tail;
    list->tail = newNode;
    list->len++;
}

void InsertDLlistHead(DLlist *list, ElementType element)
{
    //两个链表连续要当心，判断是否均存在，即链表初始化
    if(list->len == 0)
    {
        InsertDLlistTail(list,element);
    }
    else
    {
        DLNode *newNode = CreateNode(element);
        if(newNode == NULL)
        return;
        newNode->next = list->head->next;
        newNode->prev = list->head;

        list->head->next->prev = newNode;
        list->head->next = newNode;
        list->len++;
    } 
}

void RemoveByIndex(DLlist *list, int index, void (*freePtr)(ElementType))
{
    if(index < 0 || index >= list->len)
    {
        printf("删除的位置非法：%d len ： %d\n",index,list->len);
        return;
    }
    //判断前后两个节点是否都存在,即是否删去尾节点
    if(index == list->len-1)
    {
        DLNode *Prev = list->tail->prev;
        Prev->next = NULL;
        //根据ElementType类型判断是否需要清空数据域内指向的另一片空间
        if(freePtr != NULL)
        {
            freePtr(list->tail->data);
        }
        free(list->tail);
        list->tail = Prev;
    }
    else
    {
        DLNode * TravelPoint = list->head;
        for(int i = 0; i < index; i++)
        {
            TravelPoint = TravelPoint->next;
        }

        DLNode *freeNode = TravelPoint->next;
        TravelPoint->next = freeNode->next;
        freeNode->next->prev = TravelPoint;
        if(freePtr != NULL)
        {
            freePtr(freeNode->data);
        }
        free(freeNode);
    }
    list->len--;
}

void RemoveByElement(DLlist *list, ElementType element, bool(*OperPtr)(ElementType, ElementType), void (*freePtr)(ElementType))
{
    DLNode* TravelPoint = list->head;
    int index = 0;
    while(TravelPoint->next != NULL)
    {
        //t的下一个节点需要删除
        if(OperPtr(TravelPoint->next->data,element) == true)
        {
            //留下这块内存的地址，后续释放，防止内存泄漏
            RemoveByIndex(list,index,freePtr);
        }
        else
        {
            //放在这是为了防止相邻两个节点存在后者为空的情况
            index++;
            TravelPoint = TravelPoint->next;
        }
    }
}

ElementType *FindByIndex(DLlist *list,int index)
{

    if(index < 0 || index >= list->len)
    {
        printf("查找的位置非法：%d len ： %d\n",index,list->len);
        return NULL;
    }
    DLNode *TravelPoint = list->head->next;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    return &TravelPoint->data;
}

DLlist FindByElement(DLlist *list, ElementType element, bool (*OperPtr)(ElementType, ElementType))
{
    INITDLLIST(result);

    DLNode *TravelPoint = list->head;
    while(TravelPoint->next != NULL)
    {
        //t的下一个节点需要删除
        if(OperPtr(TravelPoint->next->data,element) == true)
        {
            //留下这块内存的地址，后续释放，防止内存泄漏
            InsertDLlistTail(&result,TravelPoint->next->data);
        }
        TravelPoint = TravelPoint->next;
    }
    return result;
}

void TravelDLlist(DLlist *list, void (*funcptr)(ElementType))
{
    if(funcptr == NULL)
        return;
    
    DLNode *travelPoint = list->head->next;
    while(travelPoint != NULL)
    {
        funcptr(travelPoint->data);
        travelPoint = travelPoint->next;
    }
}


void Swap(ElementType* value1,ElementType* value2)
{
    ElementType temp = *value1;
    *value1 = *value2;
    *value2 = temp;
}

void FastSort(DLNode *start,DLNode *end, bool (*funcptr)(void *,void *))
//void FastSort(struct Node *start,struct Node *end)
{
    if(start == end)
    {
        return;
    }
    //p1指向链表排序数据的开头
    DLNode *p1 = start;
    //p2指向p1后
    DLNode *p2 = start->next;

    //判断循环结束条件
    while(p2 != end)
    {
        //当p2的值比基准值小
        if(funcptr(p2->data ,start->data) == true)
        //if(p2->data < start->data)
        {
            //p1指针后移
            p1 = p1->next;
            //将比基准值小的数前移
            Swap(&p1->data,&p2->data);
        }
        p2 = p2->next;
    }
    //将基准值和p1值互换，使p1指向的值处于中间位置，即在它左边的值均比它小，在它右边的值均比它大
    Swap(&start->data,&p1->data);
    //经过一轮转换后，p1为左侧小序列的末尾，p2为右侧大序列的末尾
    FastSort(start,p1,funcptr);
    FastSort(p1->next,end,funcptr);
}

void DLlistSort(DLlist *list,bool (*funcPtr)(ElementType,ElementType))
{
    FastSort(list->head->next,NULL,funcPtr);
}

void ClearDLlist(DLlist *list, void (*clearPtr)(ElementType))
{
    while(list->head != NULL)
    {
        DLNode *next = list->head->next;
        if(list->head->data != NULL && clearPtr != NULL)
        {
            clearPtr(list->head->data);
        }
        free((list->head));
        list->head = next;
    }
    list->len = 0;
}
